/*globals jQuery */

if (!Array.prototype.indexOf)
{
  Array.prototype.indexOf = function(elt /*, from*/)
  {
    var len = this.length;

    var from = Number(arguments[1]) || 0;
    from = (from < 0)
         ? Math.ceil(from)
         : Math.floor(from);
    if (from < 0)
      from += len;

    for (; from < len; from++)
    {
      if (from in this &&
          this[from] === elt)
        return from;
    }
    return -1;
  };
}

jQuery.extend({
    /*
     * .linearInterpolate(x0,x1,y0,y1,x) returns the value of y at x on
     * the line determined by x0,x1,y0,y1
     *
     * Parameters x0,x1,y0,y1 (Float): endpoints of a straight line
     */
    linearInterpolate : function(x0, x1, y0, y1, x) {
        return y0 + (x - x0) * (y1 - y0) / (x1 - x0);
    },
    /*
     * .binarySearch(arr, val, dim) returns the index closest to the
     * given value in the array
     *
     * Parameters arr (Array): a multi dimentional array; think as an
     * array of points val (Float): value to seach for dim (Integer):
     * which sub dimension to search across
     */
    binarySearch : function(arr, val, dim) {
        var l = 0, r = arr.length - 1, x, mid;
        while (l < r) {
            mid = Math.floor((l + r) / 2);
            x = arr[mid][dim];

            if (val > x) {
                l = mid + 1;
                // r = mid-1;
            } else {
                r = mid;
            }
        }
        return l;
    },
    /*
     * .createPopupMenu(parent, items, defaultItem) returns jQuery
     * object representing the popup menu
     *
     * Parameters parent (jQuery object): the button to trigger the
     * dropdown menu items (Array): objects to put in the dropdown menu.
     * Each object must include a 'label' and 'callback' field
     * defaultItem (Integer): optional, defines the initial button that
     * is selected in the menu, if not present value is 0
     */
    createPopupMenu : function(parent, items, defaultItem) {
        var menu = jQuery("<div/>").addClass("popup-menu").css({
            left : parent.position().left,
            top : parent.position().top + parent.outerHeight()
        });

        jQuery.each(items, function(i, value) {
            menu.append(jQuery('<button/>').addClass('menu-item').text(
            value.label).button().click( function(event) {
                parent.button("option", "label", value.label);
                menu.fadeOut("fast");
                parent.button("enable");
                value.callback();
                event.stopPropagation(); // to prevent body click
                // from triggering
            }));
        });
        // Add dropdown arrow and functionality to close popup menu
        parent.button({
            icons : {
                secondary : "ui-icon-triangle-1-s"
            }
        }).click(( function(menu) {
            return function() {
                menu.fadeIn("fast");
                parent.button("disable");
                jQuery("body").click( function() { // to close menu if
                    // clicked outside
                    // of menu
                    menu.fadeOut("fast");
                    parent.button("enable");
                    jQuery("body").unbind("click");
                    event.stopPropagation(); // to prevent body
                    // click from
                    // triggering
                });
                return false;
            };
        }(menu)));
        parent.after(menu);
        parent.button("option", "label", items[defaultItem || 0].label);
        return menu;
    },
    /*
     * .calculateSize(text) returns an object with width and height
     * fields describing the width and height of the rendered text
     *
     * Parameters text (String): the String value that is to be measured
     */
    calculateSize : function(text) {
        // Calculate width of text by putting text in a div,
        // checking its width, and removing div
        var div, width, height;
        div = jQuery("<div><\/div>").css({
            display : "none",
            "font-size" : "smaller"
        }).appendTo("body").html(text);
        width = jQuery(div).outerWidth();
        height = jQuery(div).outerHeight();
        jQuery(div).remove();
        return {
            width : width,
            height : height
        };
    },
    /*
     * jQuery.parseCSV(domain,range)(rawTable) returns array full of 2D
     * points generated from the columns of rawTable as specified by the
     * domain and range arguments
     *
     * Parameters domain (String): the name of the column that
     * represents the domain of the function range (String): the name of
     * the column that represents the range of the function rawTable
     * (String): a CSV defining a table of elements, the first row are
     * the column names and successive rows are the data points
     */
    parseFullCSV : function(separator) {
        var tsv = jQuery.csv("\t", "'", "\r\n"), csv = jQuery.csv(",",
        "'", "\r\n");
        return function(rawTable) {
            var array, domainIndex, rangeIndex, domainLabel, rangeLabel, data;
            array = tsv(rawTable);
            // try to determine if the table is in tsv or csv
            // figure it out by looking at the length of the first
            // row
            if (array[0].length <= 1) {
                array = csv(rawTable);
            }
            domainIndex = 0;
            rangeIndex = 1;

            domainLabel = array[0][domainIndex];
            rangeLabel = array[0][rangeIndex];

            if (!domainLabel) {
                domainLabel = "undefined";
            }
            if (!rangeLabel) {
                rangeLabel = "undefined";
            }

            data = [];

            jQuery.each(array, function(i, points) {
                if (i === 0) { // this ignores the
                    // first set of
                    // points, which is actually the
                    // column labels
                    return true;
                }
                var x = parseFloat(points[domainIndex]), y = parseFloat(points[rangeIndex]);
                // guard against blank lines by skipping
                // over them
                if (isNaN(x) || isNaN(y)) {
                    return true;
                }
                data.push([ x, y ]);
            });
            return {
                domain : domainLabel,
                range : rangeLabel,
                points : data
            };
        };
    },
    /*
     * jQuery.parseFullCSVNoHeader(separator)(rawTable) returns array full of 2D
     * points generated from the columns of rawTable as specified by the
     * domain and range arguments
     *
     * Parameters domain (String): the name of the column that
     * represents the domain of the function range (String): the name of
     * the column that represents the range of the function rawTable
     * (String): a CSV defining a table of elements, the first row are
     * the column names and successive rows are the data points
     */
    parseFullCSVNoHeader : function(separator) {
        var tsv = jQuery.csv("\t", "'", "\r\n"), csv = jQuery.csv(",",
        "'", "\r\n");
        return function(rawTable) {
            var array, domainIndex, rangeIndex, domainLabel, rangeLabel, data;
            array = tsv(rawTable);
            // try to determine if the table is in tsv or csv
            // figure it out by looking at the length of the first
            // row
            if (array[0].length <= 1) {
                array = csv(rawTable);
            }
            data = [];

            jQuery.each(array, function(i, points) {
                // guard against blank lines by skipping
                // over them
                if (typeof points[0] === "undefined" || i === array.length-1) {
                    return true;
                }
                var x, j, row=[];
                for (j = 0; j < points.length; j+= 1) {
                    x = parseFloat(points[j]);
                    if (isNaN(x)) {
                        x = points[j];
                    }
                    row.push(x);
                }
                data.push(row);
            });
            return {
                points : data
            };
        };
    },
    /*
     * jQuery.parse1DCSV(separator)(rawTable) returns array full of 2D
     * points generated from the columns of rawTable as specified by the
     * domain and range arguments
     *
     */
    parse1DCSV : function(separator) {
        var tsv = jQuery.csv("\t", "'", "\r\n"), csv = jQuery.csv(",",
        "'", "\r\n");
        return function(rawTable) {
            var array, label, data;
            array = tsv(rawTable);
            // try to determine if the table is in tsv or csv
            // figure it out by looking at the length of the first
            // row
            if (array[0].length <= 1) {
                array = csv(rawTable);
            }
            label = array[0][0];

            data = [];

            jQuery.each(array, function(i, points) {

                if (i === 0) { // this ignores the
                    // first set of
                    // points, which is actually the
                    // column labels
                    return true;
                }
                var x = parseFloat(points[0]);
                // guard against blank lines by skipping
                // over them
                if (isNaN(x)) {
                    return true;
                }
                data.push(x);
            });
            return {
                variable: label,
                points : data
            };
        };
    },
    /*
     * jQuery.parseCSV_1d(variable,separator)(rawTable) returns 1d array of 
     * points generated from the column in rawTable defined by variable
     *
     * Parameters variable (String): the name of the column that
     * represents the column of interest
     * rawTable (String): a CSV defining a table of elements, the first row are
     * the column names and successive rows are the data points
     */
    parseCSV_1d : function(variable, separator) {
        var tsv = jQuery.csv(separator || "\t", "'", "\r\n");
        return function(rawTable) {
            var array, variableIndex, variableLabel, data;
            array = tsv(rawTable);
            // array[0] contains the column labels
            variableIndex = array[0].indexOf(variable);

            variableLabel = array[0][variableIndex];
            data = [];
            jQuery.each(array, function(i, points) {
                if (i === 0) { // this ignores the
                    // first set of
                    // points, which is actually the
                    // column labels
                    return true;
                }
                var x = parseFloat(points[variableIndex]);
                // guard against blank lines by skipping
                // over them
                if (isNaN(x)) {
                    return true;
                }
                data[i - 1] = x;
            });
            return data;
        };
    },    
    /*
     * jQuery.parseCSV(domain,range)(rawTable) returns array full of 2D
     * points generated from the columns of rawTable as specified by the
     * domain and range arguments
     *
     * Parameters domain (String): the name of the column that
     * represents the domain of the function range (String): the name of
     * the column that represents the range of the function rawTable
     * (String): a CSV defining a table of elements, the first row are
     * the column names and successive rows are the data points
     */
    parseCSV : function(domain, range, separator) {
        var tsv = jQuery.csv(separator || "\t", "'", "\r\n");
        return function(rawTable) {
            var array, domainIndex, rangeIndex, domainLabel, rangeLabel, data;
            array = tsv(rawTable);
            // array[0] contains the column labels
            domainIndex = array[0].indexOf(domain);
            rangeIndex = array[0].indexOf(range);

            domainLabel = array[0][domainIndex];
            rangeLabel = array[0][rangeIndex];
            data = [];
            jQuery
            .each(
            array, function(i, points) {

                if (i === 0) { // this ignores the
                    // first set of
                    // points, which is actually the
                    // column labels
                    return true;
                }
                var x = parseFloat(points[domainIndex]), y = parseFloat(points[rangeIndex]);
                // guard against blank lines by skipping
                // over them
                if (isNaN(x) || isNaN(y)) {
                    return true;
                }
                data[i - 1] = [ x, y ];
            });
            return data;
        };
    },
    /*
     * jQuery.mean(arr,i) Calculates the mean of the ith parameter given
     * in a multidimentional array
     *
     * Returns Float - the mean
     *
     * Parameters: arr (Array): an N element array of sub arrays
     * representing multidimentional points d (Integer): the dimension
     * to calculate the mean over
     */
    mean : function(arr, d) {
        var sum = 0;
        jQuery.each(arr, function(i, val) {
            sum += val[d];
        });
        return sum / arr.length;
    },
    /*
     * jQuery.stdev(arr,i) Calculates the standard deviation of the ith
     * parameter in a multidimentional array
     *
     * Returns Float - the standard deviation of the ith dimension
     *
     * Parameters: arr (Array): an N element array of sub arrays
     * representing multidimentional points d (Integer): the dimension
     * to calculate the mean over
     */
    stdev : function(arr, d) {
        if (arr.length <= 1) {
            return NaN;
        }
        var sum = 0, mean = jQuery.mean(arr, d);
        jQuery.each(arr, function(i, val) {
            sum += Math.pow(val[d] - mean, 2);
        });
        return Math.sqrt(sum / (arr.length - 1));
    },
    /*
     * jQuery.calculateLienarRegression Calculates the Pearson
     * product-moment correlation coefficient
     *
     * Returns Float r - the correlation coefficient
     *
     * Parameters: data (Array): N element array where each element is a
     * 2 element array representing a point.
     */
    calculateCorrelation : function(data) { // generates the linear
        // regression line
        // defined by data
        if (data.length <= 1) {
            return 0;
        }
        var n = data.length, sx, sy, meanX, meanY, sum = 0.0;
        meanX = jQuery.mean(data, 0);
        meanY = jQuery.mean(data, 1);
        sx = jQuery.stdev(data, 0);
        sy = jQuery.stdev(data, 1);
        jQuery.each(data, function(i, val) {
            sum += (val[0] - meanX) * (val[1] - meanY) / (sx * sy);
        });
        return sum / (n - 1);
    },
    /*
     * jQuery.calculateLinearRegression Calculates the linear regression
     * line (slope and y intercept) from the array of 2d points given
     *
     * Returns Object {a: y-intercept, b: slope}
     *
     * Parameters: data (Array): N element array where each element is a
     * 2 element array representing a point.
     */
    calculateLinearRegression : function(data) { // generates the
        // linear regression
        // line defined by
        // data
        var a, b, i, sx = 0, sy = 0, sx2 = 0, sxy = 0, n, x, y, minx, maxx;
        n = data.length;
        minx = data[0][0];
        maxx = minx;
        for (i = 0; i < n; i += 1) {
            x = data[i][0];
            y = data[i][1];

            minx = x < minx ? x : minx;
            maxx = x > maxx ? x : maxx;

            sx += x;
            sy += y;
            sx2 += Math.pow(x, 2);
            sxy += x * y;
        }
        b = (sxy - (sx * sy) / n) / (sx2 - sx * sx / n);
        a = sy / n - b * sx / n;

        // check to see if the data is degenerate, if so, throw an
        // exception
        if (isNaN(a) || isNaN(b)) {
            throw ("Points all equal, no slope");
        }

        return {
            bounds : [ [ minx, a + minx * b ], [ maxx, a + maxx * b ] ],
            a : a,
            b : b
        };
    },
    /*
     * jQuery.calculateRegressionSlope Calculates the slope of the
     * linear regression line from the array of 2d points given
     *
     * Returns Integer slope
     *
     * Parameters: data (Array): N element array where each element is a
     * 2 element array representing a point.
     */
    calculateRegressionSlope : function(points) {
        return jQuery.calculateLinearRegression(points).b;
    },
    /*
     * jQuery.findMinMax(array,pos) Finds the min and max bounds of the
     * given array. If the data in the array is multidimensional,
     * elementNumber specifies which one
     *
     * returns Object: {min, max}
     *
     * Parameters array (Array): an N element array with length M Array
     * elements pos (Integer): the index in the sub array to search
     * across
     */
    findMinMax : function(array, pos) {
        var range = {
            min : array[0][pos],
            max : array[0][pos]
        };
        jQuery.each(array, function(i, element) {
            range.min = (element[pos] < range.min) ? element[pos]
            : range.min;
            range.max = (element[pos] > range.max) ? element[pos]
            : range.max;
        });
        return range;
    },
    /*
     * jQuery.selection(array,n) Returns the nth element by rank out of
     * the array of Integers
     *
     * returns Integer
     *
     * Parameters array (Array): the array to search, does not need to
     * be sorted but does modify the order n (Integer): the nth element
     * by rank you are searching for
     */
    selection : function(array, n) { // selection function (pick
        // the nth value)
        function selectionHelper(array, n, left, right) {
            function partition(array, left, right, pivotIndex) { // this
                // is
                // the
                // quicksort
                // partion
                // method
                function swap(array, i, j) {
                    var x = array[i];
                    array[i] = array[j];
                    array[j] = x;
                }

                var storeIndex = left, pivotValue = array[pivotIndex], i;
                swap(array, pivotIndex, right);
                for (i = left; i < right; i += 1) {
                    if (array[i] <= pivotValue) {
                        swap(array, i, storeIndex);
                        storeIndex += 1;
                    }
                }
                swap(array, storeIndex, right);
                return storeIndex;
            }

            if (right === left) {
                return array[left];
            }

            var partitionIndex = partition(array, left, right, left);
            if (partitionIndex === n) {
                return array[n];
            }
            if (n < partitionIndex) {
                return selectionHelper(array, n, left,
                partitionIndex - 1);
            } else {
                return selectionHelper(array, n, partitionIndex + 1,
                right);
            }
        }

        return selectionHelper(array, n, 0, array.length - 1);
    },
    /*
     * Uses log selection to find the minimum element in the array
     */
    min: function(array) {
        return jQuery.selection(array,0);
    },
    /*
     * Uses log selection to find the maximum element in the array
     */
    max: function(array) {
        return jQuery.selection(array,array.length-1);
    },
    /*
     * jQuery differenceInMeans Calculates the means of vec1 and vec2 and
     * returns the floating point difference between those means
     */
    differenceInMeans: function(vec1, vec2) {
        var means = [];
        jQuery.each([vec1, vec2], function(i, vec){
            jQuery.each(vec,function(j,x) {
                if (j === 0) {
                    means[i] = x;
                } else {
                    means[i] = means[i] + x;
                }
            });
            means[i] = means[i]/vec.length;
        });
        return means[0]-means[1];
    },
    median: function(tmpPoints) {
        return ($.selection(tmpPoints,Math.floor((tmpPoints.length-1)/2))+$.selection(tmpPoints,Math.round((tmpPoints.length-1)/2)))/2;
    }
});